前言

昨天提到了基本的選Leader的方式，與log被commit的方法，感覺已經非常完整了，到底哪裡還有問題呢？

我們今天繼續往後探討當選出一個新的Leader後，真的有辦法保持Safety and Consistency嗎？

Raft

Raft Overview

0. 術語
1. Leader election
2. Normal operation (basic log replication)
3. Safety and consistency after leader changes
4. Neutralizing old leader

我們今天先介紹Safety and consistency after leader changes與Neutralizing old leader

Safety and consistency after leader changes

當一個新leader被選出時，
可能當前的每一個server儲存的log非常不一致

1. 有些可能缺少某些log entries
2. 或是因為cluster出現網路分裂的情況，有些server出現多的log entries

Raft的處理便是，不特別執行清除或是補上，而是直接執行 normal operation。原因在於，可能當一個leader被選出來時，另一個server剛好失敗，如果刻意執行清除或是補上的動作，必須等待該server重啟才能執行，反而造成等待時間的浪費。

重點:

1. normal operation 必須本身擁有修正的能力
2. Raft規定leader的logs才是正確的
3. 最終要使得所有其他的followers擁有與leader一樣的logs

注意:
leader可能在讓所有followers擁有一樣的logs過程中失效，
於是又選出新的leader，這個過程讓logs更為複雜，如下圖。

因此，更重要的重點是

只有被commited的logs是重要的，其餘還沒被commited的log都有機會被覆寫或是拋棄。

舉例:
如果上面那張圖的s2被選為leader，則幸運的情況下，最終所有的server儲存的log會與s2的一樣。

Safety Requirement

回到Raft最初的目的，我們希望的是集群中的每一個機器皆執行一樣且順序一致的指令。

當一個log entry被state machine執行時，其他的state machine執行同一個log entry時，一定也是執行同一個指令，這樣所有機器的狀態跟結果才會一樣。

Raft Safety Property

1. Leaders 不會複寫或是拋棄自己的log entries
2. 只有 leader 的 log entry可以被commited
3. entries 一定要先被 leader commited 才能給state machine執行

搭配以上性質
Raft透過自己的Safety Property來達成上述的Safety Requirement

Raft:
如果一個log entry被目前的leader決定committed(過半數都保存該log entry)，則
=> 該commited的log entry一定會存在未來的leader中

為了確保
Committed -> Present in future leaders' log

因此我們必須在剛剛提出的 Commitment, Leader election作法上做些修改與限制。

Leader Election (Revised)

上圖在進行選舉時，此時s3失效，因此整個系統不知道到底哪些entry是committed了，(log entry只儲存index, term, command沒有顯示是否committed)。

index5可能被commited了(出現在過半數的server中)或是沒有，因為此時你沒辦法確認s3的log。

但是我們為了要保證選出來的 leader，擁有之前所有已經被committed的log entries。

因此我們在選擇leader時
要選擇 最有可能包含所有已經被committed的log entries的andidates

作法:

1. Cnadidate的 RequestVote RPCs 須包含自己 最後一個log entry的 (index,term)

2. 收到 server U RequestVote RPCs的 server V，檢查

   ( last_termV > last_termU ) or
   ( last_termV == last_termU ) and ( last_indexV > last_indexU )
   

   如果自己最後一個log entry更新，term更新或是index更新。則拒絕投給該Candidates，因為自己的log更多更完整。

3. 上述保證leader一定擁有最完整的log entries

用實際例子來討論 Safety

Committing Entry from Current Term

分成兩個case討論

• case 1

s1作為leader，replicate index4至s2, s3，因此index4被committed。
此時若是要重新選舉，
- s4無法成為leader，因為他的最後一個entry的index少了4
- s5無法成為leader，因為他的最後一個term只有1，少了2

• case 2 (複雜)

1. s1 剛剛 replicate index3 到s2，還沒有replicate 到s3就crash了，因此index3沒有被commited

2. s5 還沒有被拿到index3，但是選舉時，可能得到s3, s4的票選為leader並append了3個log (s3還沒有index3，所以可以投給s5)

3. 接著，s5短暫crash又回來，s1也回來

4. 整個集群選出term4的leader為s1並append index4

5. s1 補上replicate index3到s3發現index3也滿足過半數commit了index3，執行完index3還沒通知其他followers，此時s1又crash。

結果: index3為 no safely committed

原因: 這一次的選舉s5是有可能當選的，因為s2, s3的最後一個term是2，但是s5是term3，當s5當選時，會覆蓋掉s2, s3的index3，此時s1回來則s1已經執行了index3，但是其他server的index3已經被覆蓋掉了，結果不一致。

Commitment Rules (Revised)

因此除了leader election要修改外，Commitment規則也必須修改。

Leader commit 一個log entry要求

1. 該log entry儲存在過半數的server中
2. 至少要有一個entry(包含目前leader的最新term)被儲存在過半數的server中

才能commit該log entry

如上圖，
index3被committed至少要等到index4被多數儲存，因為此時最新的term是term4
index4因為本身就包含目前leader的最新term，因此也可以直接commit

此時，s5就不能被選為leader了，因為他的term比別人小。

Log Consistency

剛剛提到 normal operation 必須本身擁有修正的能力，因為每一個server的log跟leader的log可能差很多。

先看有哪幾種Inconsistency的情況

可能有log missing或是多了leader沒有的log

1. 對於少了，要補上
2. 對於多的，要複寫掉

Repairing Followers' logs

作法:

1. leader 保存沒一個 follower 的nextIndex，表示下一個AppendEntries RPCs要送哪一個index的entry給該 follower

2. 初始化為leader的 1 + last_index

3. 如果發現 AppendEntries Consistency Check 失敗，則nextIndex遞減直到可以接上

AppendEntries Consistency Check:
Followers 一定要 擁有同樣的前一個entry的(index, term)才會儲存最新的log entry，否則就不接受該RPC

因此leader不斷往回找適當nextIndex
(a)最後會從index5開始發送
(b)最後會從index4開始發送

4. 對於有多的entries的follower從該entry之後多的都直接刪除

Neutralizing Old Leader

最後我們要來探討一個情況是，假設發生 Network Partition 使得舊的leader聯絡不上followers，導致剩餘的followers發起選舉選出新的leader

此時，舊的leader回復連線，打算commit log entries?

回到最開始提到的一個大重點 => Term 可以用來判斷新舊資訊

做法:

1. 對於每一個RPC都包含目前發送者的最新Term
2. 如果接收者發現發送者的Term更舊，就拒絕該RPC請求，回傳最新的Term
3. 發送者收到回覆退回follower，並更新成新的Term
4. 如果是接收者的Term更舊，接收者退回follower，並更新成新的Term

因此若是舊的leader回來

1. 他發送的RPC會被拒絕
2. 他收到回覆會退回follower，並更新term
3. 他的log entries會被新的leader覆蓋(反正根據剛剛的safety property，一定還沒被committed)

同時，
也因此 RequestVote RPCs 也包含新的Term，包含較舊的Term的Candidate的RPC會被拒絕，並同時被更新成新的Term。

總結

以上就是完整的Raft共識演算法，可以發現相較於Paxos，過程非常的具體，且針對每一個角色與傳送的訊息，都有詳細的定義。
因此其實照著上述的流程，是可以用任何語言來實作的此演算法的，再搭配replicate state machine，放到任何一個分散式系統便可以讓該系統利用Raft提供的一致性，最常見的例子便是Etcd，便是利用Raft讓分散式key-value儲存系統達到一致。

接下來我們會在總結一下Raft，並且會做一下這幾個共識演算法的優缺點，並介紹Zookeeper也自己設計的共識演算法 - ZAB。